Abstract: We define and study analogs of probabilistic tree embeddings and tree covers for directed graphs. We define the notion of a DAG cover of a general directed graph $G$: a small collection $D_1,\dots D_g$ of DAGs so that for all pairs of vertices $s,t$, some DAG $D_i$ provides low distortion for $\dist(s,t)$; i.e. $\dist_G(s, t) \le \min_{i \in [g]} \dist_{D_i}(s, t) \leq \alpha \cdot \dist_G(s, t)$, where $\alpha$ is the distortion.

As a trivial upper bound, there is a DAG cover with $n$ DAGs and $\alpha=1$ by taking the shortest-paths tree from each vertex. When each DAG is restricted to be a subgraph of $G$, there is a simple matching lower bound (via a directed cycle) that $n$ DAGs are necessary, even to preserve reachability. Thus, we allow the DAGs to include a limited number of additional edges not from the original graph.

When $n^2$ additional edges are allowed, there is a simple upper bound of two DAGs and $\alpha=1$. Our first result is an almost-matching lower bound that even for $n^{2-o(1)}$ additional edges, at least $n^{1-o(1)}$ DAGs are needed, even to preserve reachability. However, the story is different when the number of additional edges is $\tilde{O}(m)$, a natural setting where the sparsity of the DAG collection asymptotically matches that of the original graph. Our main upper bound is that there is a near-linear time algorithm to construct a DAG cover with $\tilde{O}(m)$ additional edges, polylogarithmic distortion, and only $O(\log n)$ DAGs. This is similar to known results for undirected graphs: the well-known FRT probabilistic tree embedding implies a tree cover where both the number of trees and the distortion are logarithmic. Our algorithm also extends to a certain probabilistic embedding guarantee. We complement our upper bound with a lower bound showing that achieving a DAG cover with no distortion and $\tilde{O}(m)$ additional edges requires a polynomial number of DAGs.

Finally, we point out that our DAG cover upper bounds have implications for a variety of combinatorial and algorithmic problems related to approximate shortest paths in directed graphs. This talk is based on joint work with Sepehr Assadi and Nicole Wein.